#q1:https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envType=study-plan-v2&envId=top-interview-150
a:https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/6833/python-di-gui-xiang-jie-by-jalan/?envType=study-plan-v2&envId=top-interview-150
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
#上述代码系统已经自己构建了所以无需再次构建
class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if len(inorder) == 0:
            return None
        tree=TreeNode(preorder[0]) #目标树对象，添加根
        mid=inorder.index(preorder[0])#mid左子树长度
        #使用了buildTree迭代，必须同初始输入buildTree(self, preorder, inorder)相同
        #确定左子树结构:左子树前序preorder[1:mid+1]，左子树中序:inorder[:mid]
        #确定右子树结构:inorder[]
        tree.left=self.buildTree(preorder[1:mid+1],inorder[:mid])
        tree.right=self.buildTree(preorder[mid+1:],inorder[mid+1:])
        return tree
#总结:
"""
类内函数嵌套调用,如何构建迭代:
def buildTree(self, preorder, inorder):
    if len(inorder) == 0:
       return None
    tree=self.buildTree(preorder[1:mid+1],inorder[:mid])
    return tree
"""

        